{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #漂亮数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果长度为 <code>n</code> 的数组 <code>nums</code> 满足下述条件，则认为该数组是一个 <strong>漂亮数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code> 是由范围 <code>[1, n]</code> 的整数组成的一个排列。</li>\n",
    "\t<li>对于每个 <code>0 &lt;= i &lt; j &lt; n</code> ，均不存在下标 <code>k</code>（<code>i &lt; k &lt; j</code>）使得 <code>2 * nums[k] == nums[i] + nums[j]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你整数 <code>n</code> ，返回长度为 <code>n</code> 的任一 <strong>漂亮数组</strong> 。本题保证对于给定的 <code>n</code> 至少存在一个有效答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>[2,1,4,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>[3,1,2,5,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-array](https://leetcode.cn/problems/beautiful-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-array](https://leetcode.cn/problems/beautiful-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        \n",
    "        def dfs(nums):\n",
    "            if len(nums) <= 2:return nums\n",
    "            a , b = [] , []\n",
    "            for i , num in enumerate(nums):\n",
    "                if i % 2 == 0:\n",
    "                    a.append(num)\n",
    "                else:\n",
    "                    b.append(num)\n",
    "            return dfs(a) + dfs(b)\n",
    "        \n",
    "        return dfs(list(range(1,n+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n):\n",
    "        nums = list(range(1, n + 1))\n",
    "\n",
    "        def dfs(nums):\n",
    "            if len(nums) <= 2:\n",
    "                return nums\n",
    "            else:\n",
    "                eves, odds = [], []\n",
    "                for i in range(0, len(nums), 2):\n",
    "                    eves.append(nums[i])\n",
    "                for i in range(1, len(nums), 2):\n",
    "                    odds.append(nums[i])\n",
    "                return dfs(odds) + dfs(eves)\n",
    "        rst = dfs(nums)\n",
    "        return rst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n==1:\n",
    "            return [1]\n",
    "        t=self.beautifulArray((n+1)//2)\n",
    "        ans=[2*i-1 for i in t]\n",
    "        if n&1:\n",
    "            t.remove((n+1)//2)\n",
    "        ans=ans+[2*i for i in t]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        t=0\n",
    "        j=0\n",
    "        i=0\n",
    "        while (n-1) >> t:\n",
    "            t+=1\n",
    "        while j<n:\n",
    "            s=(t-len(bin(i))+2)*'0'+bin(i)[2:]\n",
    "            p=s[::-1]\n",
    "            ans[j]=int('0b'+p,2)+1\n",
    "            if ans[j] <= n:\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        # 快排思想\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    left.append(lis[i])\r\n",
    "                else:\r\n",
    "                    right.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        \n",
    "        odd = self.beautifulArray((n + 1) // 2)\n",
    "        even = self.beautifulArray(n // 2)\n",
    "        \n",
    "        return [2 * x - 1 for x in odd] + [2 * x for x in even]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        # 快排思想\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        # 快排思想\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "\r\n",
    "\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        # 快排思想\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n <3:\n",
    "            return [i+1 for i in range(n)]\n",
    "        else:\n",
    "            left = self.beautifulArray(n//2+1 if n%2 else n//2)\n",
    "            right = self.beautifulArray(n//2)\n",
    "        return [c*2-1 for c in left] + [c*2 for c in right]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def beautifulArray(self, N):\n",
    "        res = [1]\n",
    "        while len(res) < N:\n",
    "            res = [i * 2 - 1 for i in res] + [i * 2 for i in res]\n",
    "        return [i for i in res if i <= N]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        memo = {1 : [1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                memo[N] = [2 * x - 1 for x in f((N + 1) // 2)] + [2 * x for x in f(N // 2)]\n",
    "            return memo[N]\n",
    "        return f(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "            \n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        ji = self.beautifulArray((n + 1) // 2)\n",
    "        ou = self.beautifulArray(n // 2)\n",
    "        return [2 * num - 1 for num in ji] + [2 * num for num in ou]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memo = {1:[1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                odds = f((N + 1)//2)\n",
    "                evens = f(N//2)\n",
    "                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return memo[N]\n",
    "        return f(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        t,j,i=0,0,0\n",
    "        while (n-1) >> t:\n",
    "            t+=1\n",
    "        while j<n:\n",
    "            ans[j]=int(bin(i)[2:].rjust(t, '0')[::-1], 2)+1\n",
    "            if ans[j] <= n:\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        t,j,i=0,0,0\n",
    "        while (n-1) >> t:\n",
    "            t+=1\n",
    "        while j<n:\n",
    "            ans[j]=int('0b'+((t-len(bin(i))+2)*'0'+bin(i)[2:])[::-1],2)+1\n",
    "            if ans[j] <= n:\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        def helper(arr: List[int]) -> List[int]:\r\n",
    "            if len(arr) <= 2:\r\n",
    "                return arr\r\n",
    "            a = helper(arr[::2])\r\n",
    "            b = helper(arr[1::2])\r\n",
    "            return a + b\r\n",
    "        return helper(list(range(1,n+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        # ans = [1]\n",
    "        # for i in range(3,n + 1,2):\n",
    "        #     mininsert = 0\n",
    "        #     maxinsert = len(ans)\n",
    "        #     dict1 = dict(zip([2*j for j in ans],list(range(len(ans)))))\n",
    "        #     temp2 = [i + k for k in ans]\n",
    "        #     for idx,key in enumerate(temp2):\n",
    "        #         if key in dict1:\n",
    "        #             if idx < dict1[key]:\n",
    "        #                 maxinsert = min(maxinsert,dict1[key])\n",
    "        #             else:\n",
    "        #                 mininsert = max(mininsert,dict1[key])\n",
    "        #     ans.insert((maxinsert + mininsert)//2 + 1,i)\n",
    "        # if n & 1 == 0:\n",
    "        #     res = [i + 1 for i in ans]\n",
    "        # else:\n",
    "        #     res = [i + 1 for i in ans if i != n]\n",
    "        # return ans + res\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "\n",
    "        m = n - 1\n",
    "        k = 1\n",
    "        while m != 1:\n",
    "            m >>= 1\n",
    "            k <<= 1\n",
    "\n",
    "        a = [0] * n\n",
    "        a[0] = 1\n",
    "        i = 1\n",
    "        t = 1\n",
    "\n",
    "        while i < n:\n",
    "            for j in range(t):\n",
    "                if a[j] + k <= n:\n",
    "                    a[i] = a[j] + k\n",
    "                    i += 1\n",
    "            t = i\n",
    "            k //= 2\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        return sorted(range(1, N + 1), key=lambda x: bin(x)[:1:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans=[i for i in range(1,n+1)]\n",
    "        def merge(ans):\n",
    "            if len(ans)==2 or len(ans)==1:\n",
    "                return ans\n",
    "            A=[]\n",
    "            B=[]\n",
    "            for i in range(len(ans)):     \n",
    "                if i%2==0:\n",
    "                    A.append(ans[i])\n",
    "                else:\n",
    "                    B.append(ans[i])\n",
    "            return merge(A)+merge(B)\n",
    "        return merge(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n==1:return [1]\n",
    "        m=n//2\n",
    "        a=self.beautifulArray(m)\n",
    "        b=self.beautifulArray(n-m)\n",
    "        \n",
    "        a=[i*2 for i in a]\n",
    "        \n",
    "        b=[i*2-1 for i in b]\n",
    "        a.extend(b)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "\n",
    "        nums = [0 for _ in range(n)]\n",
    "        left = (n+1) // 2\n",
    "        right = n - left\n",
    "        left_nums = self.beautifulArray(left)\n",
    "        right_nums = self.beautifulArray(right)\n",
    "\n",
    "        for i in range(left):\n",
    "            nums[i] = 2 * left_nums[i] - 1 \n",
    "        for j in range(right):\n",
    "            nums[left + j] = 2 * right_nums[j]\n",
    "        \n",
    "        return nums\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        if n == 1:\r\n",
    "            return [1]\r\n",
    "        mid = (n + 1) // 2\r\n",
    "        left = self.beautifulArray(mid)\r\n",
    "        right = self.beautifulArray(n - mid)\r\n",
    "        return [2 * i - 1 for i in left] + [2 * i for i in right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        def recur(nums):\n",
    "            if len(nums) <= 2:\n",
    "                return nums \n",
    "            \n",
    "            nums1 = recur(nums[::2])\n",
    "            nums2 = recur(nums[1::2])\n",
    "            return nums1 + nums2\n",
    "        \n",
    "        nums = list(range(1, n+1))\n",
    "        return recur(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.H = {}\n",
    "\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        #触底\n",
    "        if n == 1:\n",
    "            ans.append(1)\n",
    "            return ans\n",
    "        if n in self.H:\n",
    "            return self.H[n]\n",
    "\n",
    "        #递归地将子问题解决\n",
    "        left_beautiful_arry = self.beautifulArray((n + 1) // 2)\n",
    "        right_beautiful_arry = self.beautifulArray(n // 2)\n",
    "\n",
    "        #merge:\n",
    "        for val in left_beautiful_arry:\n",
    "            # 将左侧数组映射为奇数\n",
    "            ans.append(val * 2 - 1)\n",
    "        for val in right_beautiful_arry:\n",
    "            # 将右侧数组映射为偶数\n",
    "            ans.append(val * 2)\n",
    "\n",
    "        #放入哈希表\n",
    "        self.H[n] = ans\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        else:\n",
    "            left = self.beautifulArray((n + 1) // 2)\n",
    "            right = self.beautifulArray(n // 2)\n",
    "\n",
    "            return [2 * x - 1 for x in left] + [2 * x for x in right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memory = [list(range(1, n + 1))]\n",
    "        while True:\n",
    "            canbreak = True\n",
    "            new_memory = []\n",
    "            for item in memory:\n",
    "                if len(item) <= 2:\n",
    "                    new_memory.append(item)\n",
    "                else:\n",
    "                    new_memory.append(item[::2])\n",
    "                    new_memory.append(item[1::2])\n",
    "                    canbreak = False\n",
    "            if canbreak:\n",
    "                break\n",
    "            else:\n",
    "                memory = new_memory\n",
    "        result = []\n",
    "        for item in memory:\n",
    "            result.extend(item)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memo = {1:[1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                odds=f(int((N+1)/2))\n",
    "                evens=f(int(N/2))\n",
    "                memo[N] = [2*x -1 for x in odds] + [2*x for x in evens]\n",
    "            return memo[N]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mp = {1 : [1]}\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n):\n",
    "    \t\tif n in mp:\n",
    "    \t\t  return mp[n]\n",
    "    \t\tidx = 0\n",
    "    \t\tres = [0] * n\n",
    "    \t\tfor i in self.beautifulArray(int((n+1)/2)):\n",
    "    \t\t  res[idx] = 2*i - 1\n",
    "    \t\t  idx += 1\n",
    "    \t\tfor i in self.beautifulArray(int(n/2)):\n",
    "    \t\t  res[idx] = 2*i\n",
    "    \t\t  idx += 1\n",
    "    \t\tmp[n] = res\n",
    "    \t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = [1 for _ in range(n)]\n",
    "        # (1）A是一个漂亮数组，如果对A中所有元素添加一个常数，那么Ａ还是一个漂亮数组。\n",
    "\n",
    "        # (2）A是一个漂亮数组，如果对A中所有元素乘以一个常数，那么A还是一个漂亮数组。\n",
    "\n",
    "        # (3）A是一个漂亮数组，如果删除一些A中一些元素，那么A还是一个漂亮数组。\n",
    "\n",
    "        # (4) A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，\n",
    "\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            mid = l + r >> 1\n",
    "            dfs(l, mid)\n",
    "            dfs(mid + 1, r)\n",
    "            for i in range(l, mid + 1):\n",
    "                ans[i] = (ans[i] << 1) - 1\n",
    "            for i in range(mid + 1, r + 1):\n",
    "                ans[i] <<= 1\n",
    "        \n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = [1]\n",
    "        for i in range(3,n + 1,2):\n",
    "            mininsert = 0\n",
    "            maxinsert = len(ans)\n",
    "            dict1 = dict(zip([2*j for j in ans],list(range(len(ans)))))\n",
    "            temp2 = [i + k for k in ans]\n",
    "            for idx,key in enumerate(temp2):\n",
    "                if key in dict1:\n",
    "                    if idx < dict1[key]:\n",
    "                        maxinsert = min(maxinsert,dict1[key])\n",
    "                    else:\n",
    "                        mininsert = max(mininsert,dict1[key])\n",
    "            ans.insert((maxinsert + mininsert)//2 + 1,i)\n",
    "        if n & 1 == 0:\n",
    "            res = [i + 1 for i in ans]\n",
    "        else:\n",
    "            res = [i + 1 for i in ans if i != n]\n",
    "        return ans + res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        di = dict()\n",
    "        di[1] = [1]\n",
    "        def f(n):\n",
    "            if n not in di:\n",
    "                di[n] = [2 * x - 1 for x in f((n + 1) // 2)] + [2 * x for x in f(n // 2)]\n",
    "            return di[n]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        def helper(arr: List[int]) -> List[int]:\n",
    "            if len(arr) <= 2:\n",
    "                return arr\n",
    "            \n",
    "            a = helper(arr[::2])\n",
    "            b = helper(arr[1::2])\n",
    "            return a + b\n",
    "        \n",
    "        return helper(list(range(1,n+1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        # 快排思想\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N):\n",
    "        memo = {1: [1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                odds = f((N+1)//2)\n",
    "                evens = f(N//2)\n",
    "                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return memo[N]\n",
    "        return f(N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        return sorted(range(1, n + 1), key = lambda x: bin(x)[2:][::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        #构造0<=i<j<k<n\n",
    "         #漂亮数组构建满足条件\n",
    "         #1、漂亮数组等于奇数漂亮数组+偶数漂亮数组、2、奇偶漂亮数组可以向下拆分\n",
    "        memo={1:[1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                #奇数向上取整 偶数向下取整\n",
    "                memo[N] = [2*x - 1 for x in f((N+1)//2)]+[2*x for x in f(N//2)]\n",
    "            return memo[N]\n",
    "\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        memo = {1 : [1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                memo[N] = [2 * x - 1 for x in f((N + 1) // 2)] + [2 * x for x in f(N // 2)]\n",
    "            return memo[N]\n",
    "        return f(N)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        \"\"\"\n",
    "            4 = 2 * 2 = 1 + 3\n",
    "            6 = 2 * 3 = 1 + 5 = 2 + 4\n",
    "\n",
    "            3 不能在 2 和 4 的中间，不能在 1 和 5 的中间\n",
    "\n",
    "\n",
    "            如果数组 [a1, a2, ..., an] 是漂亮的，那么尽兴仿射变换后，\n",
    "            新数组 [k*a1+b, k*a2+b, ..., k*an+b] 也是漂亮的\n",
    "        \"\"\"\n",
    "\n",
    "        memo = {1: [1]}\n",
    "\n",
    "        def helper(N):\n",
    "            if N not in memo:\n",
    "                odds = helper((N+1)//2)\n",
    "                evens = helper(N//2)\n",
    "                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return memo[N]\n",
    "        return helper(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = [1]\n",
    "        for i in range(3,n + 1,2):\n",
    "            mininsert = 0\n",
    "            maxinsert = len(ans)\n",
    "            dict1 = dict(zip([2*j for j in ans],list(range(len(ans)))))\n",
    "            temp2 = [i + k for k in ans]\n",
    "            for idx,key in enumerate(temp2):\n",
    "                if key in dict1:\n",
    "                    if idx < dict1[key]:\n",
    "                        maxinsert = min(maxinsert,dict1[key])\n",
    "                    else:\n",
    "                        mininsert = max(mininsert,dict1[key])\n",
    "            ans.insert((maxinsert + mininsert)//2 + 1,i)\n",
    "        if n & 1 == 0:\n",
    "            res = [i + 1 for i in ans]\n",
    "        else:\n",
    "            res = [i + 1 for i in ans if i != n]\n",
    "        return ans + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        ans = [1 for _ in range(n)]\n",
    "        \n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            mid = l + r >> 1\n",
    "            dfs(l, mid)\n",
    "            dfs(mid + 1, r)\n",
    "            for i in range(l, mid + 1):\n",
    "                ans[i] = 2 * ans[i] - 1\n",
    "            for i in range(mid + 1, r + 1):\n",
    "                ans[i] = 2 * ans[i]\n",
    "        \n",
    "        dfs(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 分治\n",
    "    # https://leetcode.cn/problems/beautiful-array/solution/piao-liang-shu-zu-by-leetcode/\n",
    "    # https://leetcode.cn/problems/beautiful-array/solution/fen-zhi-mei-guan-jie-na-yao-xuan-hu-geng-syo6/\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        # [1]\n",
    "        # [1,2]\n",
    "        # [1,3,2]\n",
    "        # [1,3,2,4]\n",
    "        # [1,5,3,2,4]\n",
    "        # [1,5,3,2,6,4]\n",
    "        # [1,5,3,7,2,6,4]\n",
    "        # [1,5,3,7,2,6,4,8]\n",
    "        # [1,9,5,3,7,2,6,4,8]\n",
    "        # [1,9,5,3,7,2,10,6,4,8]\n",
    "        memo = {1: [1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                odds = f((N+1) // 2)\n",
    "                evens = f(N // 2)\n",
    "                memo[N] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "\n",
    "            return memo[N]\n",
    "\n",
    "        return f(N)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def beautifulArray(self, n: int) -> List[int]:\r\n",
    "        arr = [i for i in range(1, n + 1)]\r\n",
    "        def sort_arr(lis):\r\n",
    "            if len(lis) <= 1:\r\n",
    "                return(lis)\r\n",
    "            left = []\r\n",
    "            right = []\r\n",
    "            for i in range(len(lis)):\r\n",
    "                if i % 2:\r\n",
    "                    right.append(lis[i])\r\n",
    "                else:\r\n",
    "                    left.append(lis[i])\r\n",
    "            return(sort_arr(left) + sort_arr(right))\r\n",
    "        ans = sort_arr(arr)\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memo={1:[1]}\n",
    "        def f(n):\n",
    "            if n not in memo:\n",
    "                memo[n]=[2*x-1 for x in f((n+1)//2)]+[2*x for x in f(n//2)]\n",
    "            return memo[n]\n",
    "        return f(n)        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        memo = {1 : [1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                memo[N] = [2 * x - 1 for x in f((N + 1) // 2)] + [2 * x for x in f(N // 2)]\n",
    "            return memo[N]\n",
    "        return f(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]: \n",
    "        memo = {1 : [1]}\n",
    "        def f(n):\n",
    "            if n not in memo:\n",
    "                memo[n] = [2 * x - 1 for x in f((n + 1) // 2)] + [2 * x for x in f(n // 2)]\n",
    "            return memo[n]\n",
    "        return f(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    思路：将左边全为奇数,右边全为偶数并且储存答案 进行预处理\n",
    "    重要思想 做仿射变换不改变其是否为漂亮数组\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        dic = {1:[1], 0:[]}\n",
    "        def f(i):\n",
    "            if i in dic: return dic[i]\n",
    "            odd, even = (i+1)//2, i//2\n",
    "            # 对odd与even直接做变换得到左右两边的数字\n",
    "            left = [2*num-1 for num in f(odd)]\n",
    "            right = [2*num for num in f(even)]\n",
    "            dic[i] = left + right\n",
    "            return dic[i]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        # 基本情况：如果 n 等于 1，直接返回包含单个元素 1 的列表\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        \n",
    "        # 计算数组的中点\n",
    "        mid = n // 2\n",
    "        \n",
    "        # 递归调用函数，分别计算前半部分和后半部分的美丽数组\n",
    "        l = self.beautifulArray(mid)  # l 存储偶数部分的美丽数组\n",
    "        r = self.beautifulArray(n - mid)  # r 存储奇数部分的美丽数组\n",
    "        \n",
    "        # 对偶数部分的数组进行处理：将每个元素乘以 2\n",
    "        l = [i * 2 for i in l]\n",
    "        \n",
    "        # 对奇数部分的数组进行处理：将每个元素乘以 2，并减去 1\n",
    "        r = [i * 2 - 1 for i in r]\n",
    "        \n",
    "        # 返回合并后的结果，即前半部分和后半部分的美丽数组\n",
    "        return l + r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def dp(n):#递归调用\n",
    "            if n==1:\n",
    "                return [1]\n",
    "            ans=[]\n",
    "            for i in dp(n-n//2):\n",
    "                ans+=[i*2-1]\n",
    "            for j in dp(n//2):\n",
    "                ans+=[j*2]\n",
    "            return ans\n",
    "        return dp(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        emeo = {1:[1]}\n",
    "        def f(n):\n",
    "            if n not in emeo:\n",
    "                odds = f((n+1)//2)\n",
    "                evens = f(n//2)\n",
    "                emeo[n] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return emeo[n]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memo = {1 : [1]}\n",
    "        def helper(n):\n",
    "            if n not in memo:\n",
    "                odds = helper((n + 1) // 2)\n",
    "                events = helper(n // 2)\n",
    "                memo[n] = [2 * x - 1 for x in odds] + [2 * x for x in events]\n",
    "            return memo[n]\n",
    "        return helper(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        memo = {1:[1]}\n",
    "        def f(N):\n",
    "            if N not in memo:\n",
    "                odds = f((N+1)//2)\n",
    "                evens = f(N//2)\n",
    "                memo[N]=[2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return memo[N]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        emeo = {1:[1]}\n",
    "        def f(n):\n",
    "            if n not in emeo:\n",
    "                odds = f((n+1)//2)\n",
    "                evens = f(n//2)\n",
    "                emeo[n] = [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "            return emeo[n]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 1:\n",
    "                return [1]\n",
    "            return [2 * x - 1 for x in dfs((i + 1) // 2)] + [2 * x for x in dfs(i // 2)]\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        mem = {1: [1]}\n",
    "        def f(n):\n",
    "            if n not in mem:\n",
    "                mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "            return mem[n]\n",
    "\n",
    "        return f(n)\n",
    "\n",
    "        # mem = {1: [1]}\n",
    "        # def f(n):\n",
    "        #     if n not in mem:\n",
    "        #         mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "        #     return mem[n]\n",
    "        # return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n==1:return [1]\n",
    "            odds = f((n+1)//2)\n",
    "            evens = f(n//2) \n",
    "            return [2*x-1 for x in odds] + [2*x for x in evens]\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, N: int) -> List[int]:\n",
    "        m = {1 : [1]}\n",
    "        def f(N):\n",
    "            if N not in m:\n",
    "                m[N] = [2*x-1 for x in f((N+1)//2)] + [2*x for x in f(N//2)]\n",
    "            return m[N]\n",
    "        return f(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        return [2*x-1 for x in self.beautifulArray((n+1)//2)] + [2*x for x in self.beautifulArray(n//2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        mem = {1: [1]}\n",
    "        def f(n):\n",
    "            if n not in mem:\n",
    "                mem[n] = [2 * x - 1 for x in f((n + 1) // 2)] + [2 * x for x in f(n // 2)]\n",
    "            return mem[n]\n",
    "        return f(n)\n",
    "\n",
    "\n",
    "\n",
    "        # mem = {1: [1]}\n",
    "        # def f(n):\n",
    "        #     if n not in mem:\n",
    "        #         mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "        #     return mem[n]\n",
    "        # return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def dp(n):\n",
    "            if n == 1:\n",
    "                return [1]\n",
    "            ans1 = []\n",
    "            ans2 = []\n",
    "            for i in dp(n - n // 2):\n",
    "                ans1 += [i * 2 - 1]\n",
    "            for j in dp(n // 2):\n",
    "                ans2 += [j * 2]\n",
    "\n",
    "            return ans1 + ans2\n",
    "\n",
    "        return dp(n)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.beautifulArray(10))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        mem = {1: [1]}\n",
    "        def f(n):\n",
    "            if n not in mem:\n",
    "                mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "            \n",
    "            return mem[n]\n",
    "        \n",
    "        return f(n)\n",
    "\n",
    "\n",
    "        # mem = {1: [1]}\n",
    "        # def f(n):\n",
    "        #     if n not in mem:\n",
    "        #         mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "        #     return mem[n]\n",
    "        # return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "                    \n",
    "                        @cache\n",
    "                        def dfs(n):\n",
    "                            if n == 1:\n",
    "                                return [1]\n",
    "                            ans = []\n",
    "                            \n",
    "                            t = dfs(n//2)\n",
    "                            for i in t:\n",
    "                                ans.append(i*2)\n",
    "                            \n",
    "                            for i in dfs((n+1)//2):\n",
    "                                ans.append(i*2 - 1)\n",
    "                            \n",
    "                            return ans\n",
    "                        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        if n == 1:  # base case\n",
    "            return [1]\n",
    "        mid = n // 2\n",
    "        l, r = self.beautifulArray(mid), self.beautifulArray(n - mid)  # l = even, r = odd\n",
    "        l = [i * 2 for i in l]\n",
    "        r = [i * 2 - 1 for i in r]\n",
    "        return l + r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulArray(self, n: int) -> List[int]:\n",
    "        mem = {1: [1]}\n",
    "        def f(n):\n",
    "            if n not in mem:\n",
    "                mem[n] = [x * 2 - 1 for x in f((n + 1) // 2)] + [x * 2 for x in f(n // 2)]\n",
    "            return mem[n]\n",
    "        return f(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
